{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Invert Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: invertTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #翻转二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树的根节点 <code>root</code> ，翻转这棵二叉树，并返回其根节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/14/invert1-tree.jpg\" style=\"height: 165px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [4,2,7,1,3,6,9]\n",
    "<strong>输出：</strong>[4,7,2,9,6,3,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/14/invert2-tree.jpg\" style=\"width: 500px; height: 120px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [2,1,3]\n",
    "<strong>输出：</strong>[2,3,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目范围在 <code>[0, 100]</code> 内</li>\n",
    "\t<li><code>-100 &lt;= Node.val &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [invert-binary-tree](https://leetcode.cn/problems/invert-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [invert-binary-tree](https://leetcode.cn/problems/invert-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,7,1,3,6,9]', '[2,1,3]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        queue = collections.deque([root])\n",
    "\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                queue[0].left, queue[0].right = queue[0].right, queue[0].left\n",
    "\n",
    "                if queue[0].left:\n",
    "                    queue.append(queue[0].left)\n",
    "                if queue[0].right:\n",
    "                    queue.append(queue[0].right)\n",
    "\n",
    "                queue.popleft()\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def invertTree(self, root: 'TreeNode') -> 'TreeNode':\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left,root.right = self.invertTree(root.right),self.invertTree(root.left)\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def invertTree(self, root: 'TreeNode') -> 'TreeNode':\n",
    "        # recursive\n",
    "        # if root:\n",
    "        #     left_invert = self.invertTree(root.left)\n",
    "        #     right_invert = self.invertTree(root.right)\n",
    "        #     root.left = right_invert\n",
    "        #     root.right = left_invert\n",
    "        # return root\n",
    "        \n",
    "        # iterative\n",
    "        queue = []\n",
    "        if root:\n",
    "            queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "            node.left, node.right = node.right, node.left\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def invertTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not root: return\n",
    "        Tree = TreeNode(0)\n",
    "        Tree = root.left; root.left = root.right; root.right = Tree\n",
    "        self.invertTree(root.left)\n",
    "        self.invertTree(root.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def invertTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return \n",
    "        temp = root.left\n",
    "        root.left = root.right\n",
    "        root.right = temp\n",
    "        self.invertTree(root.left)\n",
    "        self.invertTree(root.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def invertTree(self, root: TreeNode) -> TreeNode: \n",
    "        result=[root]\n",
    "        while result:\n",
    "            for i in range(len(result)):\n",
    "                temp=result.pop(0)\n",
    "                if temp:\n",
    "                    temp.left,temp.right=temp.right,temp.left\n",
    "                    result.append(temp.left)\n",
    "                    result.append(temp.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def invertTree(self, root: 'TreeNode') -> 'TreeNode':\n",
    "        if not root:\n",
    "            return\n",
    "        root.left, root.right = root.right, root.left\n",
    "        self.invertTree(root.left)\n",
    "        self.invertTree(root.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def invertTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return\n",
    "        root.left,root.right=root.right,root.left\n",
    "        root.right=self.invertTree(root.right)\n",
    "        root.left=self.invertTree(root.left)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invertTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return root\n",
    "\n",
    "        if root.left:\n",
    "            self.invertTree(root.left)\n",
    "        if root.right:\n",
    "            self.invertTree(root.right)\n",
    "\n",
    "        root.left,root.right = root.right,root.left\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def invertTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return root\n",
    "        left = self.invertTree(root.left)\n",
    "        right = self.invertTree(root.right)\n",
    "        root.left, root.right = right, left\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def invertTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return\n",
    "        \n",
    "        root.right, root.left = self.invertTree(root.left), self.invertTree(root.right)\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def invertTree(self, root: TreeNode) -> TreeNode:\n",
    "        \n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            temp = root.left\n",
    "            root.left = root.right\n",
    "            root.right = temp\n",
    "\n",
    "            helper(root.left)\n",
    "            helper(root.right)\n",
    "        \n",
    "        helper(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "#用额外空间的话感觉很简单，层次遍历也可以\n",
    "class Solution:\n",
    "    def invertTree(self, root: TreeNode) -> TreeNode:\n",
    "        def traverse(root):\n",
    "            if root==None:return\n",
    "            traverse(root.left)\n",
    "            traverse(root.right)\n",
    "            root.left,root.right=root.right,root.left\n",
    "        traverse(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def invertTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return root\n",
    "        left=self.invertTree(root.right)\n",
    "        right=self.invertTree(root.left)\n",
    "        root.left,root.right=left,right\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def invertTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            pass\n",
    "\n",
    "        else:\n",
    "            root.left,root.right=root.right,root.left\n",
    "            self.invertTree(root.left)\n",
    "            self.invertTree(root.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def invertTree(self, root: TreeNode) -> TreeNode:\n",
    "        #递归\n",
    "        '''\n",
    "        if root is None:\n",
    "            return\n",
    "        root.left,root.right=self.invertTree(root.right),self.invertTree(root.left)\n",
    "        return root\n",
    "        '''\n",
    "        #迭代队列\n",
    "        import queue\n",
    "        if not root:\n",
    "            return None\n",
    "        q=queue.Queue()\n",
    "        q.put(root)\n",
    "        while not q.empty():\n",
    "            cur=q.get()\n",
    "            cur.left,cur.right=cur.right,cur.left\n",
    "            if cur.left:\n",
    "                q.put(cur.left)\n",
    "            if cur.right:\n",
    "                q.put(cur.right)\n",
    "        return root\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def invertTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root: return\n",
    "        root.left, root.right = root.right,root.left\n",
    "        self.invertTree(root.left) \n",
    "        self.invertTree(root.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def invertTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:return\n",
    "        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def invertTree(self, root):\n",
    "        if not root: # 如果节点为空，返回None\n",
    "            return \n",
    "        # 先交换节点的左右子树\n",
    "        left = self.invertTree(root.left)\n",
    "        right = self.invertTree(root.right)\n",
    "        root.left = right\n",
    "        root.right = left\n",
    "        # 然后递归交换节点的左右子树\n",
    "        return root # 返回翻转后的二叉树的根节点\n",
    "# 226"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        root.left, root.right = root.right, root.left\n",
    "\n",
    "        self.invertTree(root.left)\n",
    "        self.invertTree(root.right)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "\tdef invertTree(self, root):\n",
    "\t\t\"\"\"\n",
    "\t\t:type root: TreeNode\n",
    "\t\t:rtype: TreeNode\n",
    "\t\t\"\"\"\n",
    "\t\tif not root:\n",
    "\t\t\treturn None\n",
    "\t\t# 将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素\n",
    "\t\tqueue = [root]\n",
    "\t\twhile queue:\n",
    "\t\t\t# 每次都从队列中拿一个节点，并交换这个节点的左右子树\n",
    "\t\t\ttmp = queue.pop(0)\n",
    "\t\t\ttmp.left,tmp.right = tmp.right,tmp.left\n",
    "\t\t\t# 如果当前节点的左子树不为空，则放入队列等待后续处理\n",
    "\t\t\tif tmp.left:\n",
    "\t\t\t\tqueue.append(tmp.left)\n",
    "\t\t\t# 如果当前节点的右子树不为空，则放入队列等待后续处理\t\n",
    "\t\t\tif tmp.right:\n",
    "\t\t\t\tqueue.append(tmp.right)\n",
    "\t\t# 返回处理完的根节点\n",
    "\t\treturn root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        if not root: return None\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node: return None\n",
    "\n",
    "            cur = copy.deepcopy(node)\n",
    "\n",
    "            node.right = dfs(cur.left)\n",
    "            node.left = dfs(cur.right)\n",
    "\n",
    "            return node\n",
    "\n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from logging import root\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def invertTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return root\n",
    "        root.right, root.left = root.left, root.right\n",
    "\n",
    "        self.invertTree(root.left)\n",
    "        self.invertTree(root.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        while root:\n",
    "            tmp = root.left #用tmp暂存左节点\n",
    "            root.left = self.invertTree(root.right)\n",
    "            root.right = self.invertTree(tmp)\n",
    "            return root\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if(root==None):\n",
    "            return None\n",
    "        root.left, root.right = root.right, root.left\n",
    "        self.invertTree(root.left)\n",
    "        self.invertTree(root.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        left = root.left\n",
    "        root.left = self.invertTree(root.right)\n",
    "        root.right = self.invertTree(left)\n",
    "        return root"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
